package com.ting.test.algorithms.strings;

import java.util.ArrayList;
import java.util.HashSet;

/**
 * Created by 雷霆 on 2021/1/4.
 * <p>
 * Description：打印一个字符串的子序列
 * <p>
 * 字符串的字序列是指在一个字符串中，按顺序，但不一定连续的
 * 字符串的子串是指在一个字符串中，连续的一段字符
 * 对于一个字符串的而言，字符串中的任何一个字符在一个子序列中都有
 * 出现和不出现两种情况
 * <p>
 * 该问题最终转化为求一个树的先序遍历
 */
public class SubSequenceStr {

    public static void main(String[] args) {
        String str = "afadadf";
        ArrayList<String> list = new ArrayList();
        char[] strchar = str.toCharArray();
//        printSubSequence(strchar, 0, list, "");
//        list.forEach((subStr) -> {
//            System.out.println(subStr);
//        });

        ArrayList<String> list2 = new ArrayList();

        printAllPaiLieNoRepeat(strchar, 0, list2);
        list2.forEach((subStr) -> {
            System.out.println(subStr);
        });
    }

    private static void printSubSequence(char[] strChar, int index, ArrayList list, String path) {
        if (index == strChar.length) {
            list.add(path);
            return;
        }
        String no = path;
        printSubSequence(strChar, index + 1, list, no);
        String yes = path + strChar[index];
        printSubSequence(strChar, index + 1, list, yes);

    }

    /**
     * 打印不重复的子序列
     *
     * @param strChar
     * @param index
     * @param list
     * @param path
     */
    private static void printSubSequenceWithNoRepeat(char[] strChar, int index, HashSet list, String path) {
        if (index == strChar.length) {
            list.add(path);
            return;
        }
        String no = path;
        printSubSequenceWithNoRepeat(strChar, index + 1, list, no);
        String yes = path + strChar[index];
        printSubSequenceWithNoRepeat(strChar, index + 1, list, yes);

    }


    /**
     * 计算一个字符串的全排列
     *
     * @param str
     * @param i
     * @param response
     */
    private static void printAllPaiLie(char[] str, int i, ArrayList<String> response) {
        if (i == str.length) {
            response.add(String.valueOf(str));
        }
        for (int j = i; j < str.length; j++) {
            swap(str, i, j);
            printAllPaiLie(str, i + 1, response);
            swap(str, j, i);
        }
    }


    /**
     * 计算一个字符串的全排列
     * 去重
     *
     * @param str
     * @param i
     * @param response
     */
    private static void printAllPaiLieNoRepeat(char[] str, int i, ArrayList<String> response) {
        if (i == str.length) {
            response.add(String.valueOf(str));
        }
        boolean[] visits = new boolean[26];
        for (int j = i; j < str.length; j++) {
            if (!visits[str[j] - 'a']) {
                visits[str[j] - 'a'] = true;
                swap(str, i, j);
                printAllPaiLieNoRepeat(str, i + 1, response);
                swap(str, j, i);
            }

        }
    }

    private static void swap(char[] str, int i, int j) {
        char temp = str[i];
        str[i] = str[j];
        str[j] = temp;
    }
}
